{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "leetcode 45.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "metadata": {
        "id": "_GWyrhvAB0Qw"
      },
      "source": [
        "class Solution:\n",
        "\n",
        "    def jump(self, nums):\n",
        "        \n",
        "        cur_reach = 0\n",
        "        i, n = 0, len(nums) - 1 \n",
        "        level = 0 \n",
        "        \n",
        "        while (cur_reach < n):\n",
        "            level += 1\n",
        "            prev_reach = cur_reach \n",
        "            while (i <= prev_reach):\n",
        "                cur_reach = max(cur_reach, i + nums[i])\n",
        "                i += 1 \n",
        "        \n",
        "        return level "
      ],
      "execution_count": 43,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "K1ojgrBHB4CB",
        "outputId": "f9a1fab6-6ae7-4875-e726-491bf56cfb95",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "source": [
        "s = Solution()\n",
        "input_arr = [2,3,1,1,4]\n",
        "print(s.jump(input_arr))"
      ],
      "execution_count": 44,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "2\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}